from copy import deepcopy


class Solution:
    def partition(self, s: str) -> list:
        if len(s) == 0:
            return []
        res = [list(s)]
        huiwen_list = []
        mid_str = "*".join(list(s))
        for index in range(len(mid_str)):
            i = 1
            while True:
                if index - i < 0 or index + i >= len(mid_str):
                    break
                if mid_str[index-i:index+i+1] == mid_str[index-i:index+i+1][::-1]:
                    if (index - i) % 2 == 0:
                        huiwen_list.append([int((index-i)/2), int((index+i)/2)])
                    i += 1
                else:
                    break
        huiwen_list.sort()
        mid_huiwen_list = [[]]
        for lists in huiwen_list:
            mid_huiwen_list2 = []
            for i in range(len(mid_huiwen_list)):
                mid = deepcopy(mid_huiwen_list[i])
                if len(mid) == 0 or lists[0] > mid[-1][1]:
                    mid_huiwen_list2.append(mid + [lists])
                    continue
                if mid:
                    mid_huiwen_list2.append(deepcopy(mid))
                while len(mid) != 0 and lists[0] <= mid[-1][1]:
                    mid.pop(-1)
                mid += [lists]
                if mid not in mid_huiwen_list2:
                    mid_huiwen_list2.append(mid)
            mid_huiwen_list = mid_huiwen_list2
        for lists in mid_huiwen_list:
            length = len(lists)
            for i in range(1, 2 ** length):
                mid_str, mid_res, j = bin(i)[2:].rjust(length, "0"), [], 0
                for index, word in enumerate(mid_str):
                    if int(word):
                        mid_res += list(s[j:lists[index][0]]) + [s[lists[index][0]:lists[index][1]+1]]
                        j = lists[index][1] + 1
                mid_res += list(s[j:])
                if mid_res not in res:
                    res.append(mid_res)
        return res


a = Solution()
print(a.partition("acababa"))
print(a.partition("aab"))
b = a.partition("seeslaveidemonstrateyetartsnomedievalsees")
for lists in b:
    print(lists)
